# 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 
# 
#  
# 
#  示例 1: 
# 
#  
# 输入: nums = [0,1]
# 输出: 2
# 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 
# 
#  示例 2: 
# 
#  
# 输入: nums = [0,1,0]
# 输出: 2
# 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 10⁵ 
#  nums[i] 不是 0 就是 1 
#  
# 
#  Related Topics 数组 哈希表 前缀和 👍 774 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        """
        思路：先把数组的0转化为-1，那么具有相同数量的01就可以转化为数组和为0，进而转换为前缀和的问题
        :param nums:
        :return:
        """
        newnums = [-1 if n == 0 else 1 for n in nums]
        d = {0: -1}
        presum = 0
        maxlen = 0
        for index, num in enumerate(newnums):
            presum += num
            if presum in d:
                maxlen = max(maxlen, index - d[presum])
            else:
                d[presum] = index
        return maxlen


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().findMaxLength(nums=[0, 1,0]))
